#define _CRT_SECURE_NO_WARNINGS 1

//#include<stdio.h>
//int main()
//{
//	int r1 = 0, c1 = 0;
//	int r2 = 0, c2 = 0;
//	scanf("%d %d", &r1, &c1);
//	int arr1[r1][c1];
//	int i, j;
//	int k;
//	for (i = 0; i < r1; i++)
//	{
//		for (j = 0; j < c1; j++)
//		{
//			scanf("%d", &arr1[i][j]);
//		}
//	}
//	scanf("%d %d", &r2, &c2);
//	int arr2[r2][c2];
//	for (i = 0; i < r2; i++)
//	{
//		for (j = 0; j < c2; j++)
//		{
//			scanf("%d", &arr2[i][j]);
//		}
//	}
//	if (c1 != r2)
//	{
//		printf("Error: %d != %d\n", c1, r2);
//	}
//	else
//	{
//		int arr3[r1][c2];
//		for (i = 0; i < r1; i++)
//		{
//			for (j = 0; j < c2; j++)
//			{
//				arr3[i][j] = 0;
//			}
//		}
//		printf("%d %d\n", r1, c2);
//		for (i = 0; i < r1; i++)
//		{
//			for (j = 0; j < c2; j++)
//			{
//				for (k = 0; k < c1; k++)
//				{
//					arr3[i][j]+= arr1[i][k] * arr2[k][j];
//				}
//			}
//		}
//		for (i = 0; i < r1; i++)
//		{
//			for (j = 0; j < c2; j++)
//			{
//				if (j == 0)
//				{
//					printf("%d", arr3[i][j]);
//				}
//				else
//				{
//					printf(" %d", arr3[i][j]);
//				}
//			}
//			printf("\n");
//		}
//	}
//
//	return 0;
//}

//#include<stdio.h>
//typedef struct people
//{
//	int num;
//	int score[6];
//	double aver;
//}PEO;
//int main()
//{
//	PEO arr[10];
//	int i, j, k;
//	int t;
//	PEO temp;
//	for (i = 0; i < 10; i++)
//	{
//		arr[i].num = i + 1;
//		scanf("%d %d %d %d %d %d", &arr[i].score[0], &arr[i].score[1], &arr[i].score[2], &arr[i].score[3], &arr[i].score[4], &arr[i].score[5]);
//		for (j = 1; j < 6; j++)
//		{
//			for (k = 0; k < 6 - j; k++)
//			{
//				if (arr[i].score[k] > arr[i].score[k + 1])
//				{
//					t = arr[i].score[k + 1];
//					arr[i].score[k + 1] = arr[i].score[k];
//					arr[i].score[k] = t;
//				}
//			}
//		}
//		arr[i].aver = (arr[i].score[1] + arr[i].score[2] + arr[i].score[3] + arr[i].score[4]) / 4.0;
//	}
//	for (i = 1; i < 10; i++)
//	{
//		for (j = 0; j < 10 - i; j++)
//		{
//			if (arr[j].aver > arr[j + 1].aver)
//			{
//				temp = arr[j + 1];
//				arr[j + 1] = arr[j];
//				arr[j] = temp;
//			}
//		}
//	}
//	for (i = 9; i >= 0; i--)
//	{
//		printf("No.%-2d: %.2lf\n", arr[i].num, arr[i].aver);
//	}
//	return 0;
//}

//#include<stdio.h>
//int main()
//{
//	int h, m, s;
//	int a;
//	scanf("%d:%d:%d\n", &h, &m, &s);
//	scanf("%d", &a);
//	s += a;
//	if (s >= 60)
//	{
//		if (m == 59)
//		{
//			h += 1;
//			m = 0;
//			s -= 60;
//		}
//		else
//		{
//			m += 1;
//			s -= 60;
//		}
//	}
//	if (h >= 24)
//	{
//		h -= 24;
//		printf("%02d:%02d:%02d", h, m, s);
//	}
//	else
//	{
//		printf("%02d:%02d:%02d", h, m, s);
//	}
//	return 0;
//}

//#include<stdio.h>
//#include<math.h>
//int main()
//{
//	double x1, y1, x2, y2;
//	double x, y;
//	scanf("%lf %lf %lf %lf ", &x1, &y1, &x2, &y2);
//	x = x1 + x2;
//	y = y1 + y2;
//	if (fabs(x) < 0.05 && fabs(y) < 0.05)
//	{
//		printf("(0.0, 0.0)");
//	}
//	else if (fabs(x) < 0.05)
//	{
//		printf("(0.0, %.1lf)", y);
//	}
//	else if (fabs(y) < 0.05)
//	{
//		printf("(%.1lf, 0.0)", x);
//	}
//	else
//	{
//		printf("(%.1lf, %.1lf)", x, y);
//	}
//	return 0;
//}

//#include<stdio.h>
//typedef struct people
//{
//	char name[11];
//	double j;
//	double f;
//	double z;
//	double s;
//}PEO;
//int main()
//{
//	int n;
//	scanf("%d\n", &n);
//	PEO p[n];
//	int i;
//	for (i = 0; i < n; i++)
//	{
//		scanf("%s %lf %lf %lf\n", p[i].name, &p[i].j, &p[i].f, &p[i].z);
//		p[i].s = p[i].j + p[i].f - p[i].z;
//	}
//	for (i = 0; i < n; i++)
//	{
//		printf("%s %.2lf\n", p[i].name, p[i].s);
//	}
//	return 0;
//}


//#include<stdio.h>
//#include<string.h>
//int main()
//{
//	char ch1[81];
//	char ch2[81] = { 0 };
//	gets(ch1);
//	int n = strlen(ch1);
//	int i, j;
//	int k = 0;
//	int flag = 0;
//	for (i = 0; i < n; i++)
//	{
//		if (ch1[i] <= 'Z' && ch1[i] >= 'A')
//		{
//			flag = 1;
//			for (j = 0; j < k; j++)
//			{
//				if (ch1[i] == ch2[j])
//				{
//					break;
//				}
//			}
//			if (j >= k)
//			{
//				ch2[k] = ch1[i];
//				k++;
//			}
//		}
//	}
//	if (flag == 0)
//	{
//		printf("Not Found");
//	}
//	else
//	{
//		puts(ch2);
//	}
//	return 0;
//}


//#include<stdio.h>
//int main()
//{
//	int n;
//	int arr[n];
//	int i, j;
//	int temp;
//	scanf("%d\n", &n);
//	for (i = 0; i < n; i++)
//	{
//		scanf("%d", &arr[i]);
//	}
//	for (i = 1; i < n; i++)
//	{
//		for (j = 0; j < n - i; j++)
//		{
//			if (arr[j] > arr[j + 1])
//			{
//				temp = arr[j + 1];
//				arr[j + 1] = arr[j];
//				arr[j] = temp;
//			}
//		}
//	}
//	for (i = 0; i < n; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//	return 0;
//}


//#include<stdio.h>
//int main()
//{
//	int n;
//	scanf("%d\n", &n);
//	int a[n], b[n];
//	int i, j;
//	int k = 0;
//	int flag = 0;
//	for (i = 0; i < n; i++)
//	{
//		scanf("%d", &a[i]);
//	}
//	b[k++] = a[0];
//	for (i = 1; i < n; i++)
//	{
//		for (j = 0; j < k; j++)
//		{
//			if (a[i] == b[j])
//			{
//				flag = 1;
//				break;
//			}
//		}
//		if (flag == 0)
//		{
//			b[k++] = a[i];
//		}
//		flag = 0;
//	}
//	for (i = 0; i < k; i++)
//	{
//		if (i == 0)
//		{
//			printf("%d", b[i]);
//		}
//		else
//		{
//			printf(" %d", b[i]);
//		}
//	}
//	return 0;
//}